class Node{
    constructor(element){
        this.element = element;
        this.left = null;
        this.right = null;
    }
}


class Tree{
    constructor(){
        this.root = null;
    }

    insert(element){
        let node = new Node(element);
        if(this.root === null){
            this.root = node;
        }else{
            this.insertNode(node,this.root);
        }
    }

    insertNode(newNode,rootNode){
        if(newNode.element < rootNode.element){
            if(rootNode.left === null){
                rootNode.left = newNode;
            }else{
                this.insertNode(newNode,rootNode.left);
            }
        }else{
            if(rootNode.right === null){
                rootNode.right = newNode;
            }else{
                this.insertNode(newNode,rootNode.right);
            }
        }
    }

    min(){
        return this.minNode(this.root);
    }

    minNode(rootNode){
        while(rootNode.left != null){
            rootNode = rootNode.left;
        }
        return rootNode
    }

    max(){
        return this.maxNode(this.root);
    }

    maxNode(rootNode){
        while(rootNode.right != null){
            rootNode = rootNode.right;
        }
        return rootNode
    }

    search(element){
        return this.searchNode(element,this.root);
    }
    searchNode(element,rootNode){
        if(rootNode === null){
            return false;
        }

        if(element < rootNode.element){
            return this.searchNode(element,rootNode.left);
        }else if(element > rootNode.element){   
            return this.searchNode(element,rootNode.right);
        }else{
            return true
        }
    }

    inOrderTraverse(callback){
        this.inOrderTraverseNode(this.root,callback);
    }

    inOrderTraverseNode(node,callback){
        if(node != null){
            this.inOrderTraverseNode(node.left,callback);
            callback(node.element);
            this.inOrderTraverseNode(node.right,callback);
        }
    }

    preOrderTraverse(callback){
        this.inOrderTraverseNode(this.root,callback);
    }

    preOrderTraverseNode(node,callback){
        if(node != null){
            callback(node.element);
            this.preOrderTraverseNode(node.left,callback);
            this.preOrderTraverseNode(node.right,callback);
        }
    }

    postOrderTraverse(callback){
        this.postOrderTraverseNode(this.root,callback);
    }

    postOrderTraverseNode(node,callback){
        if(node != null){
            this.postOrderTraverseNode(node.left,callback);
            this.postOrderTraverseNode(node.right,callback);
            callback(node.element);
        }
    }

    //删除
    remove(element){
        this.root = this.removeNode(element,this.root);
    }

    removeNode(element,node){
        if(node === null){
            return null;
        }

        
        if(element < node.element){
            //1.删除的节点小于父节点
            node.left = this.removeNode(element,node.left);
            return node;
        }else if(element > node.element){
            //2.删除的节点大于父节点
            node.right = this.removeNode(element,node.right);
            return node;
        }else{
            //3.相等

            //3.1 删除叶子节点，一个子节点都没有

            if(node.left === null && node.right === null){
                node = null;
                return node;
            }

            //3.2 删除有一个子节点
            if(node.left === null){
                node = node.right;
                return node;
            }else if(node.right === null){
                node = node.left;
                return node;
            }

            //3.3 删除有两个子节点的节点

            //3.3.1 找最小子节点
            let endNode = this.minNode(node.right);
            node.element = endNode.element;
            //3.3.2 
            node.right = this.removeNode(endNode.element,node.right)
            return node;
        }
    }

    depth(){
        return this.maxDepth(this.root);
    }

    maxDepth(root) {
        if (root === null) { //注意等号
            return 0;
        } else {
            var leftDepth = this.maxDepth(root.left),
                rightDepth = this.maxDepth(root.right);
    
            var childDepth = leftDepth > rightDepth ? leftDepth : rightDepth;
    
            return childDepth + 1;//根节点不为空高度至少为1
        }
    }
}

let tree = new Tree();

tree.insert(11);
tree.insert(7)
tree.insert(5);
tree.insert(3);
tree.insert(6);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(15);
tree.insert(13);
tree.insert(20);
tree.insert(12);
tree.insert(14);
tree.insert(18);
tree.insert(25);

console.log(tree.depth());

// console.log(tree.min());
// console.log(tree.max());

// console.log(tree.search(11));

// console.log(tree.search(19));

// let list = [];

// let callback = (element) => {
//     console.log(element)
//     list.push(element);
// }
// tree.preOrderTraverse(callback);
// console.log(list)



// tree.remove(6);
// tree.remove(5);
// tree.remove(15);
// console.log(tree);

